package ninetwentyfour;

import java.util.Stack;

public class Solution {

    public static class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        init(head);
        Solution solution = new Solution();
        ListNode listNode = solution.swapPairs(head);

    }

    private static void init(ListNode head) {
        ListNode tail = head;
        for(int i = 1; i < 5; i++) {
            ListNode tmp =  new ListNode(i);
            tail.next = tmp;
            tail = tail.next;
        }
    }

    public  ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode newHead = new ListNode(0);
        ListNode tail = newHead;
        ListNode cur = head, nex = cur.next, nnext = nex.next;

        while(cur != null && nex != null){
            tail.next = nex;
            nex.next = cur;
            cur.next = nnext;

            tail = cur;
            cur = nnext;

            if(cur != null){
                nex = cur.next;
            }
            if(nex != null){
                nnext = nex.next;
            }
        }
        return newHead.next;
    }

    public static ListNode swapPairs1(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode newHead = head;
        ListNode cur = head;
        ListNode tail = newHead;
        ListNode len = head;
        int length = 0;
        while(len != null){
            length++;
            len = len.next;
        }

        for(int i = 0; i < length; i+=2){
            while(cur != null && cur.next != null){
                stack.push(cur);
                cur = cur.next;
                stack.push(cur);
            }
            while(!stack.empty()){
                ListNode tmp = stack.pop();
                tail.next = tmp;
                tail = tail.next;
            }
        }
        if(cur != null){
            tail.next = cur;
        }

        return newHead.next;
    }

}
